package 剑指offer;

public class 构建乘积数组 {
//    暴力法 超时
//    public int[] constructArr(int[] a) {
//        int[] res = new int[a.length];
//        for (int i = 0; i < a.length; i++) {
//            int ans=1;
//            for (int j = 0; j < a.length; j++) {
//                if (j==i)
//                    continue;
//                ans*=a[j];
//            }
//            res[i]=ans;
//        }
//        return res;
//    }
        public int[] constructArr(int[] a) {
            int[] ans = new int[a.length];
            //乘以左半部分
            for (int i = 0,cur=1; i < a.length; i++) {
                 ans[i]=cur;
                 cur*=a[i];
            }
            for (int i = a.length-1,cur=1; i >=0 ; i--) {
                ans[i]*=cur;
                cur*=a[i];
            }
            return ans;
        }
}
